package 第六周;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xhw
 */

public class 组合总和 {
    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> result = combinationSum(candidates, target);
        System.out.println(result); // 输出: [[7], [2, 2, 3]]
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); // 排序有助于优化
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
        if (remain < 0) {
            return; // 如果剩余数为负数，说明这条路径不正确，回溯
        } else if (remain == 0) {
            result.add(new ArrayList<>(tempList)); // 找到一个正确的组合
        } else {
            for (int i = start; i < candidates.length; i++) {
                tempList.add(candidates[i]); // 选择当前数
                backtrack(result, tempList, candidates, remain - candidates[i], i); // 递归探索
                tempList.remove(tempList.size() - 1); // 撤销选择
            }
        }
    }
}
